#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct Node
{
    int x, y, cost;
    Node( int _x, int _y, int _cost )
        : x( _x ), y( _y ), cost( _cost ) { }
    Node( ) { }
};

vector<Node> f[ 10001 ];
int p, c, d[ 10001 ];

void init( )
{
    int i, j, x, y, c1, c2;
    scanf("%d%d", &p, &c);
    for ( i = 0; i <= p; i++ )
        f[ i ].clear( );
    for ( i = 1; i <= p; i++ )
    {
        scanf("%d", &c1);
        f[ 0 ].push_back( Node( 0, i, c1 ) );
    }
    for ( i = 0; i < c; i++ )
    {
        scanf("%d%d%d%d", &x, &y, &c1, &c2);
        f[ x + 1 ].push_back( Node( x + 1, y + 1, c1 ) );
        f[ y + 1 ].push_back( Node( y + 1, x + 1, c2 ) );
    }
/*
    for ( i = 0; i <= p; i++ )
    {
        for ( j = 0; j < f[ i ].size( ); j++ )
            printf("%d %d %d\n", f[ i ][ j ].x, f[ i ][ j ].y, f[ i ][ j ].cost);
        printf("\n");
    }
*/
}

bool relax( int x, int y, int cost )
{
    if ( d[ x ] + cost < d[ y ] )
    {
        d[ y ] = d[ x ] + cost;
        return true;
    }
    return false;
}

void spfa( )
{
    int i, t;
    queue<int> q;
    for ( i = 1; i <= p; i++ )
        d[ i ] = 0xfffffff;
    d[ 0 ] = 0;
    q.push( 0 );
    while ( !q.empty( ) )
    {
        t = q.front( );
        q.pop( );
        for ( i = 0; i < f[ t ].size( ); i++ )
            if ( relax( f[ t ][ i ].x, f[ t ][ i ].y, f[ t ][ i ].cost ) )
                q.push( f[ t ][ i ].y );
    }
}

void print( int t )
{
    int i, r = 1;
    for ( i = 2; i <= p; i++ )
        if ( d[ r ] < d[ i ] )
            r = i;
    printf("Scenario #%d:\n%d\n\n", t, r - 1);
}

int main( )
{
    int i, t;
    scanf("%d", &t);
    for ( i = 1; i <= t; i++ )
    {
        init( );
        spfa( );
        print( i );
    }
    return 0;
}
